#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE  10
typedef int Elemtype;
//静态顺序表
typedef struct SqList01
{
   Elemtype pList[MAXSIZE];
   int length;
   int listSize;
}SqList01;

//动态的顺序表
typedef struct SqList02
{
    Elemtype *pList;
    int length;
    int listSize;
}SqList02;

//初始化顺序表
void initSqList(SqList02 *L){
    L->pList = (Elemtype *)malloc(sizeof(Elemtype) * MAXSIZE);
    L->length = 0;
    L->listSize = MAXSIZE;
}

//第i个元素前面插入e
int insert(SqList02 *L,Elemtype e,int index){

    if(index < 1 || index > L->length){
        return 0;
    }
    //没有空间
    if(L->length >= L->listSize){
        Elemtype* pNew =  (Elemtype *)malloc(sizeof(Elemtype) * MAXSIZE*2);
        for (int i = 0; i < L->length; i++)
        {//把数据复制到新的空间
            pNew[i] =  L->pList[i];
        }
        L->pList = pNew;
        L->listSize = MAXSIZE*2; 
    }
    //有空间,插入元素操作
    for (int i = L->length-1; i>=index-1; i--)
    {
        L->pList[i+1]=L->pList[i];
    }
    L->pList[index-1] = e;
    L->length++;
    return 1;
}
//删除第index个元素
int delete(SqList02 *L,int index){
    if(index < 1 || index > L->length){
        return 0;
    }
    for (int i = index-1; i<L->length-1 ; i++)
    {
       L->pList[i] = L->pList[i+1];
    }
    L->length--;
    return 1;
}

int deleteMin(SqList02 *L){
    int min = 0;
    for (int i = 1; i < L->length; i++)
    {
        if(L->pList[i]<L->pList[min]){
            min = i;
        }
    }
    L->pList[min] = L->pList[L->length-1];
    L->length--;
}
//删除 s-t的值
int deleteElem(SqList02 *L,int s,int t){
    int curLength = 0;
    for (int i = 0; i < L->length; i++)
    {
        if(L->pList[i]<s || L->pList[i]>t){
            L->pList[curLength++] = L->pList[i];
        }
    }
    L->length = curLength;
    return 1;
}

int deleteA(SqList02 *L,int s,int t){
    int start = 0;
    int last = L->length-1;
    //从前往找第一个符合删除范围的元素索引
    for ( int i = 0; i < L->length; i++)
    {
        if(L->pList[i] >=s && L->pList[i] <= t){
            start = i;
            break;
        }
    }
    //从后往前找最后一个符合删除范围的元素索引
  for ( int i = L->length-1; i >=0; i--)
    {
        if(L->pList[i] >=s && L->pList[i]<=t){
            last = i;
            break;
        }
    }
    //偏移
    //删除的元素个数、偏移的距离
    int k = last - start +1;
    for (int i = last+1; i < L->length; i++)
    {
        L->pList[i-k] = L->pList[i];
    }
    L->length -= k;
    return 1;
}

//删除 s-t的值
int deleteElems(SqList02 *L){
    int curLength = 0;
    for (int i = 0; i < L->length; i++)
    {//过滤条件
        if(L->pList[i]!=L->pList[curLength-1]){
            L->pList[curLength++] = L->pList[i];
        }
    }
    L->length = curLength;
    return 1;
}
//最小值法合并两表为第三个表
int combine(SqList02 * La,SqList02 * Lb,SqList02 *Lc){
    Lc->pList = (Elemtype*)malloc(sizeof(Elemtype) * (La->length + Lb->length));
    Lc->length = 0;
    Lc->listSize = La->length + Lb->length;
    int i,j;
    int curLength = 0;
    //最小值
    for (i=0,j=Lb->length-1; i >=La->length|| j< 0 ; )
    {
       if(La->pList[i]<=Lb->pList[j]){
        //A更小
        Lc->pList[curLength++] = La->pList[i];
        i++;
       }
       if (La->pList[i]>Lb->pList[j])
       {
        Lc->pList[curLength++] = Lb->pList[j];
        j--;
       }
    }
    while(i<La->length){
        Lc->pList[curLength++] = La->pList[i];
        i++;
    }
    while (j>=0)
    {
       Lc->pList[curLength++] = Lb->pList[j];
        j--;
    }
    Lc->length = curLength;
    //可以将La和Lb都释放掉，并让listSize值为0，这里省略不写了
    return 1;
}
//最大值法合并两表A，B成一个表A，A空间大

//将 A，B合并到表A，升序
int combineByMax(SqList02 * La,SqList02 * Lb){
    int i = La->length-1;
    int j = 0;
    int curLength = 0; //新插入的元素个数
    while ( i>=0 && j<Lb->length)
    {
        if(La->pList[i] > Lb->pList[j]){
            //A表值更大
            La->pList[La->listSize-1-curLength] = La->pList[i];
            i--;
        }else{
             La->pList[La->listSize-1-curLength] = Lb->pList[j];
             j++;
        }
         curLength++;
    }
    //B未遍历完
    while (j < Lb->length)
    {
        La->pList[La->listSize-1-curLength] = Lb->pList[j];
         j++;
         curLength++;
    }
    //A未遍历完，但是A剩余的值就不需要再移动。
    La->length += Lb->length;
    return 1;
}

//插入排序（部分）
int insertSort(SqList02 * L,int r){
    int i,j;
    for (int i = r; i < L->length; i++)
    {
       int temp = L->pList[i];
       for ( j = i-1; j>=0; j--)
       {
            if(L->pList[j] <= temp){
                break;
            }
            L->pList[j+1] = L->pList[j];
       }
            L->pList[j+1] = temp; 
    }
    return 1;
}

//用过滤法求交集
int insertsect(SqList02 * La,SqList02 * Lb){
    int curLength = 0;
    int i=0,j=0;
    while (i<La->length && j<Lb->length)
    {
       if(La->pList[i] > Lb->pList[j]){
            j++;
       }else if(La->pList[i] < Lb->pList[j]){
            i++;
       }else{ //a=b
            La->pList[curLength++] = La->pList[i];
            i++; j++;
       }
    }
    La->length = curLength;
    return 1;
}
//求A与B的差集，必须用一个新表存储
int except(SqList02 * La,SqList02 * Lb,SqList02 * Lc){
    int curLength = 0; // 表C的长度
    int i=0,j=0;
    while (i<La->length && j<Lb->length)
    {
       if(La->pList[i] > Lb->pList[j]){
           Lc->pList[curLength++] = Lb->pList[j++];
       }else if(La->pList[i] < Lb->pList[j]){
           Lc->pList[curLength++] = La->pList[i++];
       }else{ 
           i++; j++;
       }
    }
    while (i<La->length)
    {
         Lc->pList[curLength++] = La->pList[i++];
    }
    while (j<Lb->length)
    {
        Lc->pList[curLength++] = Lb->pList[j++];
    }
    Lc->length =curLength;
    return 1;
}
//逆置
int reverse(SqList02 * La,int startIndex,int lastIndex){
    int i=startIndex,j =lastIndex;
    while (i<j)
    {
        int temp = La->pList[i];
        La->pList[i] = La->pList[j];
        La->pList[j] = temp; 
        i++; j--;
    }
    return 1;
}

void print(SqList02 * L){
    printf("this Sqlist : length is %d , listSize = %d \n",L->length,L->listSize);
    for (int i = 0; i < L->length; i++)
    {
        printf(" %d ",L->pList[i]);
    }
    printf("\n");
}

int main(){
    SqList02 la,lb,Lc;
    int a[7]={1,2,3,4,5,6,7};
    int b[3]={2,4,9}; 
    la.listSize = 7;
    la.length = 7;
    lb.listSize =3;
    lb.length=3;
    la.pList =a;
    lb.pList =b;
    Lc.length = 0;
    Lc.pList = (Elemtype*)malloc(sizeof(Elemtype)*MAXSIZE);
    Lc.listSize = MAXSIZE;
    int r = 3;
    reverse(&la,0,la.length-1);
    reverse(&la,0,la.length-r-1);
    reverse(&la,la.length-r,la.length-1);
    print(&la);
    return 0;
}